/*
--------------KMP算法--------------
用于在字符串S中匹配字符串T

注：
此模板的字符串都是从第0位开始存的
但返回和输出的位置都是以第1位为开始的！! 

*/

#include<iostream>
#include<string>
#include<string.h>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
using namespace std;
#define ll long long
#define pi acos(-1)
const int maxn = 1e6+5;


int nnext[maxn];   //用于匹配失败时指针跳转
char s[maxn];   //主字符串S
char t[maxn];   //待匹配的模式串T 


inline void getnext()  //获得next数组 
{
	// next的计算依赖于字符串t 
	int t1 = 0;
	int t2 = -1;
	nnext[0] = -1;
	int len = strlen(t);
	while(t1<len)
	{
		if(t2==-1||t[t1]==t[t2])
			nnext[++t1] = ++t2;
		else
			t2 = nnext[t2];
	}
}

inline int kmp1()   //kmp算法---返回第一个匹配的位置 
{
	getnext();   //得到next数组
	
	int i = 0;
	int j = 0;
	int len1 = strlen(s);
	int len2 = strlen(t);
	
	while(i<len1&&j<len2)
	{
		if(j==-1||s[i]==t[j])
		{
			++i;
			++j;
		}
		else j = nnext[j];
	}
	
	if(j>=len2) //匹配成功，返回位置
		return i-len2+1;   //这里的+1对应上面的注意事项 
	else
		return -1; 
	 
}

inline int kmp2()   //kmp算法---输出全部匹配的位置 
{
	int result = 0;

	getnext();   //得到next数组
	
	int i = 0;
	int j = 0;
	int len1 = strlen(s);
	int len2 = strlen(t);
	
	int book = 0; 
	
	while(i<len1)
	{
		if(j==-1||s[i]==t[j])
		{
			++i;
			++j;
		}
		else j = nnext[j];
		
		if(j==len2)
		{
			//这里的+1对应上面的注意事项
//			cout<<i-j+1<<endl;   //输出匹配到的位置 
			++result; 
			j = nnext[j];
			book = 1;
		}
	}
	
	return result;
	//如果到这里book值仍为0，则匹配失败
}

signed main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",t);
		scanf("%s",s);
		memset(nnext,0,sizeof(nnext));
		printf("%d\n",kmp2());
	}
	return 0;
}